https://www.acmicpc.net/problem/1929

아래처럼 단순히 중첩 반복문으로 풀면 시간 초과됨

m, n = map(int, input().split())

prime_list = []

for i in range(m, n + 1):
    if i > 1:
        # 반복마다 True로 초기화됨
        isPrime = True
        # 자기 자신을 포함하면 i % i == 0까지 가기 때문에 i는 제외해야 함
        for j in range(2, i):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            prime_list.append(i)

for prime in prime_list:
    print(prime)

2를 제외한 짝수 필터링, 제곱근까지만 곱해보는 방식으로 최적화

# 1. 1과 자기 자신으로 나누었을 때만 나머지가 0임
# 2. 그 외의 숫자들로 나누었을 때는 나머지가 0이 아닌 값을 구해야 함
# 3. 2를 제외한 모든 짝수는 소수가 아님
# 4. 제곱근까지만 곱해보면 소수인지 아닌지 판별할 수 있음

m, n = map(int, input().split())

prime_list = []

for i in range(m, n + 1):
    if i == 2:
        prime_list.append(i)
    elif i % 2 == 0:
        continue
    elif i > 1:
        isPrime = True
        for j in range(2, int(i**0.5) + 1):
            if i % j == 0:
                isPrime = False
                break
        if isPrime:
            prime_list.append(i)

for prime in prime_list:
    print(prime)

에라토스테네스의 체 알고리즘을 사용한 답변

m, n = map(int, input().split())

is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False  # 0과 1은 소수가 아님

# 에라토스테네스의 체 알고리즘
for i in range(2, int(n**0.5) + 1):
    if is_prime[i]:
        for j in range(i*i, n + 1, i):
            is_prime[j] = False

prime_list = [i for i in range(m, n + 1) if is_prime[i]]

for prime in prime_list:
    print(prime)